//二叉搜索树
//搜索和插入的思路和之前用c++做的那个差不多，这里就不再实现一遍了，但是为了实现一遍红黑树，
//所以这里的代码用那个老师的，然后在这基础上进行修改实现红黑树
//二叉树的结构和quicksort的排序结构差不多，可以方便用这点来做数学上的分析
//但是这种普通二叉树有缺点，就是无法随机化得到输入，也就是说，可能输入是带有正序或者逆序这种
//这种对于二叉树来说很差的输入，最终会导致不好的性能
//二叉树还有种方法是，返回一个key的rank，这个可以通过给每个节点添加一个属性node计算其子节点个数来完成
//遍历可以通过队列来完成
//这里删除的办法是，用右子树最小节点去替换被删节点 hibbard deletion
//这个删除办法的弊端是树会变得越来越不平衡,结果就是时间复杂度是n的开平方
//下面是大佬代码
/******************************************************************************
 *  Compilation:  javac BST.java
 *  Execution:    java BST
 *  Dependencies: StdIn.java StdOut.java Queue.java
 *  Data files:   https://algs4.cs.princeton.edu/32bst/tinyST.txt
 *
 *  A symbol table implemented with a binary search tree.
 *
 *  % more tinyST.txt
 *  S E A R C H E X A M P L E
 *
 *  % java BST < tinyST.txt
 *  A 8
 *  C 4
 *  E 12
 *  H 5
 *  L 11
 *  M 9
 *  P 10
 *  R 3
 *  S 0
 *  X 7
 *
 ******************************************************************************/
 
import edu.princeton.cs.algs4.*;

import java.util.NoSuchElementException;

 /**
  *  The {@code BST} class represents an ordered symbol table of generic
  *  key-value pairs.
  *  It supports the usual <em>put</em>, <em>get</em>, <em>contains</em>,
  *  <em>delete</em>, <em>size</em>, and <em>is-empty</em> methods.
  *  It also provides ordered methods for finding the <em>minimum</em>,
  *  <em>maximum</em>, <em>floor</em>, <em>select</em>, <em>ceiling</em>.
  *  It also provides a <em>keys</em> method for iterating over all of the keys.
  *  A symbol table implements the <em>associative array</em> abstraction:
  *  when associating a value with a key that is already in the symbol table,
  *  the convention is to replace the old value with the new value.
  *  Unlike {@link java.util.Map}, this class uses the convention that
  *  values cannot be {@code null}—setting the
  *  value associated with a key to {@code null} is equivalent to deleting the key
  *  from the symbol table.
  *  <p>
  *  It requires that
  *  the key type implements the {@code Comparable} interface and calls the
  *  {@code compareTo()} and method to compare two keys. It does not call either
  *  {@code equals()} or {@code hashCode()}.
  *  <p>
  *  This implementation uses an (unbalanced) <em>binary search tree</em>.
  *  The <em>put</em>, <em>contains</em>, <em>remove</em>, <em>minimum</em>,
  *  <em>maximum</em>, <em>ceiling</em>, <em>floor</em>, <em>select</em>, and
  *  <em>rank</em>  operations each take &Theta;(<em>n</em>) time in the worst
  *  case, where <em>n</em> is the number of key-value pairs.
  *  The <em>size</em> and <em>is-empty</em> operations take &Theta;(1) time.
  *  The keys method takes &Theta;(<em>n</em>) time in the worst case.
  *  Construction takes &Theta;(1) time.
  *  <p>
  *  For alternative implementations of the symbol table API, see {@link ST},
  *  {@link BinarySearchST}, {@link SequentialSearchST}, {@link RedBlackBST_my},
  *  {@link SeparateChainingHashST}, and {@link LinearProbingHashST},
  *  For additional documentation, see
  *  <a href="https://algs4.cs.princeton.edu/32bst">Section 3.2</a> of
  *  <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
  *
  *  @author Robert Sedgewick
  *  @author Kevin Wayne
  */
 public class BST<Key extends Comparable<Key>, Value> {
     public Node root;             // root of BST

     private class Node {
         private Key key;           // sorted by key
         private Value val;         // associated data
         private Node left, right;  // left and right subtrees
         private int size;          // number of nodes in subtree

         public Node(Key key, Value val, int size) {
             this.key = key;
             this.val = val;
             this.size = size;
         }
     }

     /**
      * Initializes an empty symbol table.
      */
     public BST() {
     }

     /**
      * Returns true if this symbol table is empty.
      * @return {@code true} if this symbol table is empty; {@code false} otherwise
      */
     public boolean isEmpty() {
         return size() == 0;
     }

     /**
      * Returns the number of key-value pairs in this symbol table.
      * @return the number of key-value pairs in this symbol table
      */
     public int size() {
         return size(root);
     }

     // return number of key-value pairs in BST rooted at x
     private int size(Node x) {
         if (x == null) return 0;
         else return x.size;
     }

     /**
      * Does this symbol table contain the given key?
      *
      * @param  key the key
      * @return {@code true} if this symbol table contains {@code key} and
      *         {@code false} otherwise
      * @throws IllegalArgumentException if {@code key} is {@code null}
      */
     public boolean contains(Key key) {
         if (key == null) throw new IllegalArgumentException("argument to contains() is null");
         return get(key) != null;
     }

     /**
      * Returns the value associated with the given key.
      *
      * @param  key the key
      * @return the value associated with the given key if the key is in the symbol table
      *         and {@code null} if the key is not in the symbol table
      * @throws IllegalArgumentException if {@code key} is {@code null}
      */
     public Value get(Key key) {
         return get(root, key);
     }

     private Value get(Node x, Key key) {
         if (key == null) throw new IllegalArgumentException("calls get() with a null key");
         if (x == null) return null;
         int cmp = key.compareTo(x.key);
         if      (cmp < 0) return get(x.left, key);
         else if (cmp > 0) return get(x.right, key);
         else              return x.val;
     }

     /**
      * Inserts the specified key-value pair into the symbol table, overwriting the old
      * value with the new value if the symbol table already contains the specified key.
      * Deletes the specified key (and its associated value) from this symbol table
      * if the specified value is {@code null}.
      *
      * @param  key the key
      * @param  val the value
      * @throws IllegalArgumentException if {@code key} is {@code null}
      */
     public void put(Key key, Value val) {
         if (key == null) throw new IllegalArgumentException("calls put() with a null key");
         if (val == null) {
             delete(key);
             return;
         }
         root = put(root, key, val);
         assert check();
     }

     private Node put(Node x, Key key, Value val) {
         if (x == null) return new Node(key, val, 1);
         int cmp = key.compareTo(x.key);
         if      (cmp < 0) x.left  = put(x.left,  key, val);
         else if (cmp > 0) x.right = put(x.right, key, val);
         else              x.val   = val;
         x.size = 1 + size(x.left) + size(x.right);
         return x;
     }


     /**
      * Removes the smallest key and associated value from the symbol table.
      *
      * @throws NoSuchElementException if the symbol table is empty
      */
     public void deleteMin() {
         if (isEmpty()) throw new NoSuchElementException("Symbol table underflow");
         root = deleteMin(root);
         assert check();
     }

     private Node deleteMin(Node x) {
         if (x.left == null) return x.right;
         x.left = deleteMin(x.left);
         x.size = size(x.left) + size(x.right) + 1;
         return x;
     }

     /**
      * Removes the largest key and associated value from the symbol table.
      *
      * @throws NoSuchElementException if the symbol table is empty
      */
     public void deleteMax() {
         if (isEmpty()) throw new NoSuchElementException("Symbol table underflow");
         root = deleteMax(root);
         assert check();
     }

     private Node deleteMax(Node x) {
         if (x.right == null) return x.left;
         x.right = deleteMax(x.right);
         x.size = size(x.left) + size(x.right) + 1;
         return x;
     }

     /**
      * Removes the specified key and its associated value from this symbol table
      * (if the key is in this symbol table).
      *
      * @param  key the key
      * @throws IllegalArgumentException if {@code key} is {@code null}
      */
     public void delete(Key key) {
         if (key == null) throw new IllegalArgumentException("calls delete() with a null key");
         root = delete(root, key);
         assert check();
     }

     private Node delete(Node x, Key key) {
         if (x == null) return null;

         int cmp = key.compareTo(x.key);
         if      (cmp < 0) x.left  = delete(x.left,  key);
         else if (cmp > 0) x.right = delete(x.right, key);
         else {
             if (x.right == null) return x.left;
             if (x.left  == null) return x.right;
             Node t = x;
             x = min(t.right);
             x.right = deleteMin(t.right);
             x.left = t.left;
         }
         x.size = size(x.left) + size(x.right) + 1;
         return x;
     }


     /**
      * Returns the smallest key in the symbol table.
      *
      * @return the smallest key in the symbol table
      * @throws NoSuchElementException if the symbol table is empty
      */
     public Key min() {
         if (isEmpty()) throw new NoSuchElementException("calls min() with empty symbol table");
         return min(root).key;
     }

     private Node min(Node x) {
         if (x.left == null) return x;
         else                return min(x.left);
     }

     /**
      * Returns the largest key in the symbol table.
      *
      * @return the largest key in the symbol table
      * @throws NoSuchElementException if the symbol table is empty
      */
     public Key max() {
         if (isEmpty()) throw new NoSuchElementException("calls max() with empty symbol table");
         return max(root).key;
     }

     private Node max(Node x) {
         if (x.right == null) return x;
         else                 return max(x.right);
     }

     /**
      * Returns the largest key in the symbol table less than or equal to {@code key}.
      *
      * @param  key the key
      * @return the largest key in the symbol table less than or equal to {@code key}
      * @throws NoSuchElementException if there is no such key
      * @throws IllegalArgumentException if {@code key} is {@code null}
      */
     public Key floor(Key key) {
         if (key == null) throw new IllegalArgumentException("argument to floor() is null");
         if (isEmpty()) throw new NoSuchElementException("calls floor() with empty symbol table");
         Node x = floor(root, key);
         if (x == null) throw new NoSuchElementException("argument to floor() is too small");
         else return x.key;
     }

     private Node floor(Node x, Key key) {
         if (x == null) return null;
         int cmp = key.compareTo(x.key);
         if (cmp == 0) return x;
         if (cmp <  0) return floor(x.left, key);
         Node t = floor(x.right, key);
         if (t != null) return t;
         else return x;
     }

     public Key floor2(Key key) {
         Key x = floor2(root, key, null);
         if (x == null) throw new NoSuchElementException("argument to floor() is too small");
         else return x;

     }

     private Key floor2(Node x, Key key, Key best) {
         if (x == null) return best;
         int cmp = key.compareTo(x.key);
         if      (cmp  < 0) return floor2(x.left, key, best);
         else if (cmp  > 0) return floor2(x.right, key, x.key);
         else               return x.key;
     }

     /**
      * Returns the smallest key in the symbol table greater than or equal to {@code key}.
      *
      * @param  key the key
      * @return the smallest key in the symbol table greater than or equal to {@code key}
      * @throws NoSuchElementException if there is no such key
      * @throws IllegalArgumentException if {@code key} is {@code null}
      */
     public Key ceiling(Key key) {
         if (key == null) throw new IllegalArgumentException("argument to ceiling() is null");
         if (isEmpty()) throw new NoSuchElementException("calls ceiling() with empty symbol table");
         Node x = ceiling(root, key);
         if (x == null) throw new NoSuchElementException("argument to ceiling() is too large");
         else return x.key;
     }

     private Node ceiling(Node x, Key key) {
         if (x == null) return null;
         int cmp = key.compareTo(x.key);
         if (cmp == 0) return x;
         if (cmp < 0) {
             Node t = ceiling(x.left, key);
             if (t != null) return t;
             else return x;
         }
         return ceiling(x.right, key);
     }

     /**
      * Return the key in the symbol table of a given {@code rank}.
      * This key has the property that there are {@code rank} keys in
      * the symbol table that are smaller. In other words, this key is the
      * ({@code rank}+1)st smallest key in the symbol table.
      *
      * @param  rank the order statistic
      * @return the key in the symbol table of given {@code rank}
      * @throws IllegalArgumentException unless {@code rank} is between 0 and
      *        <em>n</em>–1
      */
     public Key select(int rank) {
         if (rank < 0 || rank >= size()) {
             throw new IllegalArgumentException("argument to select() is invalid: " + rank);
         }
         return select(root, rank);
     }

     // Return key in BST rooted at x of given rank.
     // Precondition: rank is in legal range.
     private Key select(Node x, int rank) {
         if (x == null) return null;
         int leftSize = size(x.left);
         if      (leftSize > rank) return select(x.left,  rank);
         else if (leftSize < rank) return select(x.right, rank - leftSize - 1);
         else                      return x.key;
     }

     /**
      * Return the number of keys in the symbol table strictly less than {@code key}.
      *
      * @param  key the key
      * @return the number of keys in the symbol table strictly less than {@code key}
      * @throws IllegalArgumentException if {@code key} is {@code null}
      */
     public int rank(Key key) {
         if (key == null) throw new IllegalArgumentException("argument to rank() is null");
         return rank(key, root);
     }

     // Number of keys in the subtree less than key.
     private int rank(Key key, Node x) {
         if (x == null) return 0;
         int cmp = key.compareTo(x.key);
         if      (cmp < 0) return rank(key, x.left);
         else if (cmp > 0) return 1 + size(x.left) + rank(key, x.right);
         else              return size(x.left);
     }

     /**
      * Returns all keys in the symbol table in ascending order,
      * as an {@code Iterable}.
      * To iterate over all of the keys in the symbol table named {@code st},
      * use the foreach notation: {@code for (Key key : st.keys())}.
      *
      * @return all keys in the symbol table in ascending order
      */
     public Iterable<Key> keys() {
         if (isEmpty()) return new Queue<Key>();
         return keys(min(), max());
     }

     /**
      * Returns all keys in the symbol table in the given range
      * in ascending order, as an {@code Iterable}.
      *
      * @param  lo minimum endpoint
      * @param  hi maximum endpoint
      * @return all keys in the symbol table between {@code lo}
      *         (inclusive) and {@code hi} (inclusive) in ascending order
      * @throws IllegalArgumentException if either {@code lo} or {@code hi}
      *         is {@code null}
      */
     public Iterable<Key> keys(Key lo, Key hi) {
         if (lo == null) throw new IllegalArgumentException("first argument to keys() is null");
         if (hi == null) throw new IllegalArgumentException("second argument to keys() is null");

         Queue<Key> queue = new Queue<Key>();
         keys(root, queue, lo, hi);
         return queue;
     }

     private void keys(Node x, Queue<Key> queue, Key lo, Key hi) {
         if (x == null) return;
         int cmplo = lo.compareTo(x.key);
         int cmphi = hi.compareTo(x.key);
         if (cmplo < 0) keys(x.left, queue, lo, hi);
         if (cmplo <= 0 && cmphi >= 0) queue.enqueue(x.key);
         if (cmphi > 0) keys(x.right, queue, lo, hi);
     }

     /**
      * Returns the number of keys in the symbol table in the given range.
      *
      * @param  lo minimum endpoint
      * @param  hi maximum endpoint
      * @return the number of keys in the symbol table between {@code lo}
      *         (inclusive) and {@code hi} (inclusive)
      * @throws IllegalArgumentException if either {@code lo} or {@code hi}
      *         is {@code null}
      */
     public int size(Key lo, Key hi) {
         if (lo == null) throw new IllegalArgumentException("first argument to size() is null");
         if (hi == null) throw new IllegalArgumentException("second argument to size() is null");

         if (lo.compareTo(hi) > 0) return 0;
         if (contains(hi)) return rank(hi) - rank(lo) + 1;
         else              return rank(hi) - rank(lo);
     }

     /**
      * Returns the height of the BST (for debugging).
      *
      * @return the height of the BST (a 1-node tree has height 0)
      */
     public int height() {
         return height(root);
     }
     private int height(Node x) {
         if (x == null) return -1;
         return 1 + Math.max(height(x.left), height(x.right));
     }

     /**
      * Returns the keys in the BST in level order (for debugging).
      *
      * @return the keys in the BST in level order traversal
      */
     public Iterable<Key> levelOrder() {
         Queue<Key> keys = new Queue<Key>();
         Queue<Node> queue = new Queue<Node>();
         queue.enqueue(root);
         while (!queue.isEmpty()) {
             Node x = queue.dequeue();
             if (x == null) continue;
             keys.enqueue(x.key);
             queue.enqueue(x.left);
             queue.enqueue(x.right);
         }
         return keys;
     }

   /*************************************************************************
     *  Check integrity of BST data structure.
     ***************************************************************************/
     private boolean check() {
         if (!isBST())            StdOut.println("Not in symmetric order");
         if (!isSizeConsistent()) StdOut.println("Subtree counts not consistent");
         if (!isRankConsistent()) StdOut.println("Ranks not consistent");
         return isBST() && isSizeConsistent() && isRankConsistent();
     }

     // does this binary tree satisfy symmetric order?
     // Note: this test also ensures that data structure is a binary tree since order is strict
     private boolean isBST() {
         return isBST(root, null, null);
     }

     // is the tree rooted at x a BST with all keys strictly between min and max
     // (if min or max is null, treat as empty constraint)
     // Credit: elegant solution due to Bob Dondero
     private boolean isBST(Node x, Key min, Key max) {
         if (x == null) return true;
         if (min != null && x.key.compareTo(min) <= 0) return false;
         if (max != null && x.key.compareTo(max) >= 0) return false;
         return isBST(x.left, min, x.key) && isBST(x.right, x.key, max);
     }

     // are the size fields correct?
     private boolean isSizeConsistent() { return isSizeConsistent(root); }
     private boolean isSizeConsistent(Node x) {
         if (x == null) return true;
         if (x.size != size(x.left) + size(x.right) + 1) return false;
         return isSizeConsistent(x.left) && isSizeConsistent(x.right);
     }

     // check that ranks are consistent
     private boolean isRankConsistent() {
         for (int i = 0; i < size(); i++)
             if (i != rank(select(i))) return false;
         for (Key key : keys())
             if (key.compareTo(select(rank(key))) != 0) return false;
         return true;
     }


     /**
      * Unit tests the {@code BST} data type.
      *
      * @param args the command-line arguments
      */
     public static void main(String[] args) {
         BST<String, Integer> st = new BST<String, Integer>();
         for (int i = 0; !StdIn.isEmpty(); i++) {
             String key = StdIn.readString();
             st.put(key, i);
         }

         for (String s : st.levelOrder())
             StdOut.println(s + " " + st.get(s));

         StdOut.println();

         for (String s : st.keys())
             StdOut.println(s + " " + st.get(s));
     }
 }

 /******************************************************************************
  *  Copyright 2002-2025, Robert Sedgewick and Kevin Wayne.
  *
  *  This file is part of algs4.jar, which accompanies the textbook
  *
  *      Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne,
  *      Addison-Wesley Professional, 2011, ISBN 0-321-57351-X.
  *      http://algs4.cs.princeton.edu
  *
  *
  *  algs4.jar is free software: you can redistribute it and/or modify
  *  it under the terms of the GNU General Public License as published by
  *  the Free Software Foundation, either version 3 of the License, or
  *  (at your option) any later version.
  *
  *  algs4.jar is distributed in the hope that it will be useful,
  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  *  GNU General Public License for more details.
  *
  *  You should have received a copy of the GNU General Public License
  *  along with algs4.jar.  If not, see http://www.gnu.org/licenses.
  ******************************************************************************/
